#include<iostream>
using namespace std;
void Tway_Sort(int arr[], int n)
{
	int temp[1010];
	int head, tail;
	head = tail = 0;
	temp[0] = arr[0];
	for (int i = 1; i < n; i++) {
		if (temp[0] > arr[i]) {
			head = (head - 1 + n) % n;
		    temp[head] = arr[i];
		}
		else if (temp[0] < arr[i]) {
			tail = (tail + 1 + n) % n;
			temp[tail] = arr[i];
		}
		else {
			int j;
			tail++;
			temp[tail] = temp[tail - 1];
			for (j = tail - 1; arr[j] < temp[(j - 1 + n) % n]; j--) {
				temp[j] = temp[(j - 1 + n) % n];
			}
			temp[j] = arr[i];
		}
	}
	for (int i = 0; i < n; i++) {
		arr[i] = temp[head];
		head = (head + 1 + n) % n;
	}
}